package leetcode.Hot100;

import leetcode.TreeNode;
import leetcode.TreeNodeUtil;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Cheng Jun
 * Description: 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，
 * 同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
 *
 * 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，
 * 你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/19 0:32
 */
public class Codec2 {
    public static void main(String[] args) {
        Codec2 codec2 = new Codec2();
        TreeNode root = TreeNodeUtil.getBT(new Object[]{1,null,2, null,null,3});
        System.out.println(codec2.serialize(root));
        System.out.println(codec2.deserialize(codec2.serialize(root)));
    }


    // Encodes a tree to a single string.
    //       1
    //   2        3
    // null 4   5  null
    // 1,2,3,null,4,5,null,null,null,null,null
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();
            if (poll != null) {
                sb.append(poll.val + ",");
                queue.add(poll.left);
                queue.add(poll.right);
            }else {
                // null 用 x 表示
                sb.append("x,");
            }
        }
        // 去掉末尾 ","
        sb.deleteCharAt(sb.length() -1);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == "") {
            return null;
        }
        // data 封装到队列中，等会再出列
        Queue<String> dataQueue = new LinkedList<>(Arrays.asList(data.split(",")));
        // 首先出列头元素，构成 root 节点
        TreeNode root = new TreeNode(Integer.valueOf(dataQueue.poll()));

        // 设置 root 的左右子节点，然后还要不断的设置 左右子节点的 左右子节点 一直设置到 dataQueue 中无元素
        // 这种 不断重复做一件事，让我们又想到了使用队列
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);
        while (!nodeQueue.isEmpty()){
            // 当前节点
            TreeNode curNode = nodeQueue.poll();
            // 一次出两个，分别为左右子节点
            String left = dataQueue.poll();
            String right = dataQueue.poll();
            // 不为x 就是不为 null，为当前节点curNode 设置左右子节点
            if (!left.equals("x")) {
                TreeNode leftNode = new TreeNode(Integer.valueOf(left));
                curNode.left = leftNode;
                // 同理，子节点需要入列，等待设置其左右子节点
                nodeQueue.add(leftNode);
            }
            if (!right.equals("x")) {
                TreeNode rightNode = new TreeNode(Integer.valueOf(right));
                curNode.right = rightNode;
                // 同理，子节点需要入列，等待设置其左右子节点
                nodeQueue.add(rightNode);
            }
        }
        return root;
    }


}
